#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CSTree.h"
#define MaxVertNum 10


typedef char* InfoType;

typedef struct Node2{
    //指向的顶点位置在图的数组中的下标
    int adjVert;
    //下一条临边
    struct Node2 *nextEdge;
}EdgeNode;

typedef struct Node1{
    //顶点信息
    InfoType vertInfo;
    //邻接的首个边
    EdgeNode *nextEdge;
}VertNode;

typedef struct{
    //顶点为头结点的单链表存储所有边
    VertNode verts[MaxVertNum];
    //边的个数和点的个数
    int vertNum, edgeNum;
}ALGraph;

//根据节点信息查找在邻接表中的下标
int findVertIndex(ALGraph G, InfoType info){
    for(int i = 0; i < G.vertNum; i++){
        if(strcmp(G.verts[i].vertInfo, info) == 0){
            return i;
        }
    }
    return -1;
}

//以邻接表存储的无向图
void createUDALGraph(ALGraph &G){
    printf("-----输入顶点个数、边的个数：-----\n");
    scanf("%d %d", &G.vertNum, &G.edgeNum);
    
    printf("-----输入顶点信息-----\n");
    for(int i = 0; i < G.vertNum; i++){
        G.verts[i].nextEdge = NULL;
        G.verts[i].vertInfo = (InfoType)malloc(100);
        scanf("%s", G.verts[i].vertInfo);
    }

    //输入边
    printf("-----输入边-----\n");
    int cnt;
    InfoType info = (InfoType)malloc(100);
    while(true){
        printf("输入点邻接的边数(-1结束输入边):");
        scanf("%d", &cnt);
        if(cnt == -1)
            break;
        printf("输入顶点:");
        scanf("%s", info);
        int index1 = findVertIndex(G, info);
        //表头
        VertNode *p = &G.verts[index1];
        //以头插法建立单链表
        for(int i = 0; i < cnt; i++){
            printf("输入邻接点：");
            scanf("%s", info);
            //顶点到邻接点
            int index2 = findVertIndex(G, info);
            EdgeNode *node2 = (EdgeNode *)malloc(sizeof(EdgeNode));
            *node2 = {index2, p->nextEdge};
            p->nextEdge = node2;
            //邻接点到顶点
            EdgeNode *node1 = (EdgeNode *)malloc(sizeof(EdgeNode));
            *node1 = {index1, G.verts[index2].nextEdge};
            G.verts[index2].nextEdge = node1;
        }
    }
}

int visted[MaxVertNum] = {0};
void DFSTree(ALGraph G, int i, CSTree &T);
void DFSForest(ALGraph G, CSTree &T){
    T = NULL;
    int i;
    CSTree p, q;
    for(i = 0; i < G.vertNum; i++) visted[i] = 0;

    for(i = 0; i < G.vertNum; i++){
        if(!visted[i]){
            p = (CSTree)malloc(sizeof(CSNode));
            *p = {G.verts[i].vertInfo, NULL, NULL};
            if(!T) T = p;
            else q->nextSibling = p;
            q = p;
            DFSTree(G, i, p);
        }
    }
}

void DFSTree(ALGraph G, int i, CSTree &T){
    visted[i] = 1;
    bool first = true;
    EdgeNode *e;
    CSTree p, q;
    e = G.verts[i].nextEdge;
    while(e){
        if(!visted[e->adjVert]){
            p = (CSTree)malloc(sizeof(CSNode));
            *p = {G.verts[e->adjVert].vertInfo, NULL, NULL};
            if(first){
                T->firstChild = p;
                first = false;
            }else{
                q->nextSibling = p;
            }
            q = p;
            DFSTree(G, findVertIndex(G, q->Info), q);
        }
        e = e->nextEdge;
    }
}
// void dfs(ALGraph G, int i){
//     //访问i节点
//     printf("%s", G.verts[i].vertInfo);
//     visted[i] = 1;
//     //访问 i 节点邻接的所有边
//     EdgeNode *p = G.verts[i].nextEdge;
//     //邻接边指向的节点 在点数组中的下标
//     int index;
//     while(p){
//         if(!visted[p->adjVert]){
//             dfs(G, p->adjVert);
//         }
//         p = p->nextEdge;
//     }
// }
// void DFS(ALGraph G){
//     for(int i = 0; i < G.vertNum; i++) visted[i] = 0;
//     for(int i = 0; i < G.vertNum; i++){
//         if(!visted[i])
//             dfs(G, i);
//     }
// }





